1. Field of the Invention
The present invention relates to a computing device, a method, and a computer program product for performing a square computation and a (q^l+q^l′) multiplication in a finite field.
2. Description of the Related Art
Methods are known that use cryptography to protect information sent over a communication path. Some methods using cryptography require a key to be shared with a communication partner in advance. In a method such as this, it is troublesome to share and manage the key. On the other hand, a method using public key cryptography can realize secure communication without requiring a key to be shared in advance. Therefore, the method using public key cryptography is widely used as a basic technology for network security. Information terminals are becoming more diverse. Various schemes and protocols using a public key are being used in small devices through innovations in methods and packaging. For example, a method is proposed for compressing public key size and encrypted data size in public key cryptography (refer to K. Rubin and A Silverberg, “Torus-Based Cryptography”, CRYPTO 2003, LNCS 2729, 349-365, 2003). A basis of the method is that, when a subset, referred to as an algebraic torus, in a set of numbers used in public key cryptography is used, an element of the set can be represented by a small number of bits.
A method is also proposed in which a square computation of an algebraic torus is performed at a high speed (refer to M. Stam and A. K. Lenstra, “Efficient Subgroup Exponentiation in Quadratic and Sixth Degree Extensions” CHES 2002, LNCS 2523, 318-332, 2002). In the method proposed in “Efficient Subgroup Exponentiation in Quadratic and Sixth Degree Extensions”, in an algebraic torus that is a subgroup in a sixth degree extension field, a square in a pseudo-polynomial base is taken by a base field being multiplied nine times. Ordinarily, multiplication is calculated by 18 operations, and the square is calculated by 12 operations. Therefore, computation speed is increased in the method described in “Efficient Subgroup Exponentiation in Quadratic and Sixth Degree Extensions”. When a root of a modulus f(x) is z, {1, z, z^2, z^3, z^4, z^5} is referred to as a polynomial base, and {z, z^2, z^3, z^4, z^5, z^6} is referred to as a pseudo-polynomial base. Here, the symbol ‘^’ represents power, and ‘z^a’ indicates z to the a-th power.
Effective cryptographic protocols, such as a signature scheme, are configured using pairing (refer to D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the Weil pairing” Asiacrypt 2001, LNCS 2248, 514-532, 2001). Pairing computation involves two steps: (1) an ambiguous pairing computation (such as Miller's algorithm), and (2) elimination of ambiguity (final exponentiation). For the final exponentiation, a method is proposed in which calculation when ‘r=3’ can be performed at a high speed (refer to M. Shirase, T. Takagi, and E. Okamoto, “Final Exponentiation for ηT Pairing”, The Institute of Electronics, Information, and Communication Engineers Technical Report ISEC 2006-98). In the method proposed in “Final Exponentiation for ηT Pairing”, in an algebraic torus that is a subgroup in a sixth degree extension field, a (q+1) multiplication is realized by a base field multiplied nine times. A base is a combination of a polynomial base of a quadratic extension and a polynomial base of a cubic extension. Thus, an example is known in which a speed of a square computation and a (q+1) multiplication is increased using a characteristic in which an element is the element of an algebraic torus T6(Fq). To use the method described in “Efficient Subgroup Exponentiation in Quadratic and Sixth Degree Extensions” in torus compression public key cryptography, a base (polynomial base of the quadratic extension and polynomial base of the cubic extension) ordinarily used for compression and expansion is required to be converted to a pseudo-polynomial base. As a result of a conversion such as this, an overhead occurs. Therefore, in torus compression public key cryptography such as this, the square computation is preferably performed at a high speed on a finite field. Similarly, in pairing, the square computation and (q^1+q^1′) multiplication are preferably performed at a high speed on a finite field.